Developer CD Series 1994 November: Tool Chest/Dev.CD Nov 94.toast/New System Software Extensions/Thread Manager Extension 2.0.1/Sample Applications/Power Examples/SortPicts/Source/QuickSort.cp

Text File | 1994-06-03 | 4.3 KB | 192 lines | [TEXT/MPS ]

/*----------------------------------------------------------------------------

    QuickSort.cp

    fastQSort() is a replacement for qsort().  Compared with the Think C library
    version of qsort, fastQSort is about 3 times faster (it takes 1/3 the time),
    and its speed isn't dependent on the data being sorted.

    One problem with qsort is that when the data is not in random order -- for
    example when it's already ordered, in reverse order, or almost sorted -- then
    qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can
    take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort
    algorithm doesn't have this problem, because it randomly selects the pivot
    element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.

    Also, because fastQSort doesn't exhibit worst case behavior, it doesn't
    require as much stack space, even though it has 12 bytes more of local
    variables.

    The things that make fastQSort so much faster than qsort are:

    1)    fastQSort picks the pivot element randomly, so it doesn't display worst
        case behavior.

    2)    fastQSort uses pointers and pointer arithmetic, avoiding multiplication
        whenever possible.

    3)    qsort uses std_swap() to swap the data between two locations, and
        std_swap loops through the data 3 times to perform the exchange!  In
        comparison, swapMem() loops through the data just once.

    4)    fastQSort uses register variables whenever it makes good sense to do so.


    Researched and written by:

        Haydn Huntley
        Haydn's Consulting
        203 West Stone
        Fairfield, Iowa  52556
        [phone]

    During the school year, I may be reached at the following address:

        Haydn Huntley
        Eigenmann Hall #289
        Indiana University
        Bloomington, IN  47406
        [phone]

    E-mail:  [e-mail]

    This version was modified by Randy Thelen of Apple Computer, Inc.
    This version works within the shell of SortPicts.

    Hopefully, we'll see faster Sorts with QuickSort than with Heap sorts and the like
----------------------------------------------------------------------------*/

#include "GWorldObj.h"
#include "QuickSort.h"

#define    Data    sortListPtr

void    GWorldObj::QuickSort( void)
{
    long            *tickPtr = (long *)0x16A;
    char            mmuMode = true32b;

    SetTitle( (const unsigned char*)"\pQuick Sorting");

    SwapMMUMode( &mmuMode);
    UseGWorld();
#ifdef DEMO
    //    This offsets for drawing directly to the screen
    offscreenPtr -= (long) ((**(((CWindowPtr)me)->portPixMap)).bounds.top * pictRowBytes) +
                    (**(((CWindowPtr)me)->portPixMap)).bounds.left;
#endif

    HLock( (Handle)sortList);
    sortListPtr = *sortList;
    if( !sortListPtr)
        return;

    yieldTime = *tickPtr + gYieldDelay;

    QuickSortEngine( 0, N, &mmuMode);

    UnuseGWorld();
    SwapMMUMode( &mmuMode);

    HUnlock( (Handle)sortList);
    SetTitle( (const unsigned char*)"\pDone");

    doneSorting = true;
    finishedTime = TickCount();
    DrawObj();
}


void    GWorldObj::ChooseMedian( long a, long b, long c)
{
    long        m;        //    median

    if( Data[a] > Data[b])
        if( Data[a] > Data[c])
            if( Data[b] > Data[c])
                m = b;
            else
                m = c;
        else
            m = a;
    else
        if( Data[a] > Data[c])
            m = a;
        else
            if( Data[b] > Data[c])
                m = c;
            else
                m = b;

    if( a != m)
        ExchangeSortItem( a, m);
}


void    GWorldObj::QuickSortEngine( long left, long right, char *mmuMode)
{
    long            n;
    long            i, j;

    if( doneSorting)
        return;

    while( (n = right - left) > 1)
    {
        if( n < kPivotCutoff)        //    Use a random pivot
            ExchangeSortItem( left + RandomPixel( n), left);
        else
            ChooseMedian( left, left + (n >> 1),
                          left + RandomPixel( n));

        i = left;
        j = right;

        while( 1)
        {
            i++;
            while( (i < right) && (Data[i] < Data[left]))
                i++;

            j--;
            while( (j > left) && (Data[j] > Data[left]))
                j--;

            if( i >= j)
                break;

            ExchangeSortItem( i, j);
        }

        if( j == left)
        {
            left++;
            continue;
        }

        ExchangeSortItem( left, j);
        if( (j - left) < (right - (j + 1)))
        {
            /* equivalent to doFastQSort (j + qSize, last);        */
            /* to save stack space                                */
            QuickSortEngine( left, j, mmuMode);
            left = j + 1;
        }
        else
        {
            /* equivalent to doFastQSort (first, j);            */
            /* to save stack space                                */
            QuickSortEngine( j+1, right, mmuMode);
            right = j;
        }

        if( YieldIfTime( mmuMode))
        {
            doneSorting = true;
            return;
        }
    }

}